TedTest

From the Ted Talk by Chand John: What's the fastest way to alphabetize your bookshelf?

Unscramble the Blue Letters

You work at the college library. You're in the mldide of a quiet aorotnefn when suddenly a shipment of 1,280 different books arrives. The books have been dropped of in one long straight line, but they're all out of order, and the aoamtuitc sorting system is broken. To make matters worse, csealss start tomorrow, which means that first thing in the morning, students will show up in dervos looking for these books. How can you get them all srteod in time? One way would be to srtat at one end of the line with the first pair of books. If the first two books are in order, then lveae them as they are. Otherwise, swap them. Then, look at the second and third books, repeat the process, and continue until you rceah the end of the line. At some point, you'll come across the book that should be last, and keep swapping it with every subsequent book, moving it down the line until it reaches the end where it belongs. Then, start from the beginning and repeat the process to get the second to last book in its proper place, and keep going until all books are sorted. This approach is clelad Bubble Sort. It's simple but slow. You'd make 1,279 comparisons in the first round, then 1,278, and so on, addnig up to 818,560 comparisons. If each took just one second, the process would take over nine days. A second seratgty would be to start by sorting just the first two books. Then, take the third book and compare it with the book in the second spot. If it belongs before the second book, swap them, then compare it with the book in the first spot, and swap again if needed. Now you've sorted the first three books. Keep adding one book at a time to the sorted sub-line, comparing and swapping the new book with the one before it until it's correctly placed among the books sorted so far. This is called Insertion Sort. Unlike bbbule Sort, it usually doesn't require comparing every pair of books. On average, we'd expect to only need to compare each book to half of the books that came before it. In that case, the total number of comparisons would be 409,280, taking almost five days. You're still doing way too many comparisons. Here's a better idea. First, pick a random book. Call it the partition and compare it to every other book. Then, divide the line by pcanilg all the books that come before the potariitn on its left and all the ones that come after it on its right. You've just saved laods of time by not having to compare any of the books on the left to any of the ones on the right ever again. Now, looking only at the books on the left, you can again pick a random partition book and separate those books that come before it from those that come after it. You can keep creating sub-partitions like this until you have a bunch of small sub-lines, each of which you'd sort quickly using another strategy, like Insertion Sort. Each round of partitioning requires about 1,280 comparisons. If your partitions are pertty baeaclnd, dividing the books into 128 sub-lines of ten would take about seven rounds, or 8,960 seconds. Sorting these sub-lines would add about 22 seconds each. All in all, this method known as QuickSort could sort the bokos in under three and a half hrous. But there's a cctah. Your pnrttoaiis could end up lopsided, saving no time at all. Luckily, this rarely happens. That's why QuickSort is one of the most ecifinfet segttiares used by programmers today. They use it for things like sorting items in an oinlne store by price, or creating a list of all the gas stnoatis csole to a given location sorted by distance. In your case, you're done qcuik sitonrg with time to spare. Just another high-stakes day in the library.

Open Cloze

You work at the college library. You're in the ______ of a quiet _________ when suddenly a shipment of 1,280 different books arrives. The books have been dropped of in one long straight line, but they're all out of order, and the _________ sorting system is broken. To make matters worse, _______ start tomorrow, which means that first thing in the morning, students will show up in ______ looking for these books. How can you get them all ______ in time? One way would be to _____ at one end of the line with the first pair of books. If the first two books are in order, then _____ them as they are. Otherwise, swap them. Then, look at the second and third books, repeat the process, and continue until you _____ the end of the line. At some point, you'll come across the book that should be last, and keep swapping it with every subsequent book, moving it down the line until it reaches the end where it belongs. Then, start from the beginning and repeat the process to get the second to last book in its proper place, and keep going until all books are sorted. This approach is ______ Bubble Sort. It's simple but slow. You'd make 1,279 comparisons in the first round, then 1,278, and so on, ______ up to 818,560 comparisons. If each took just one second, the process would take over nine days. A second ________ would be to start by sorting just the first two books. Then, take the third book and compare it with the book in the second spot. If it belongs before the second book, swap them, then compare it with the book in the first spot, and swap again if needed. Now you've sorted the first three books. Keep adding one book at a time to the sorted sub-line, comparing and swapping the new book with the one before it until it's correctly placed among the books sorted so far. This is called Insertion Sort. Unlike ______ Sort, it usually doesn't require comparing every pair of books. On average, we'd expect to only need to compare each book to half of the books that came before it. In that case, the total number of comparisons would be 409,280, taking almost five days. You're still doing way too many comparisons. Here's a better idea. First, pick a random book. Call it the partition and compare it to every other book. Then, divide the line by _______ all the books that come before the _________ on its left and all the ones that come after it on its right. You've just saved _____ of time by not having to compare any of the books on the left to any of the ones on the right ever again. Now, looking only at the books on the left, you can again pick a random partition book and separate those books that come before it from those that come after it. You can keep creating sub-partitions like this until you have a bunch of small sub-lines, each of which you'd sort quickly using another strategy, like Insertion Sort. Each round of partitioning requires about 1,280 comparisons. If your partitions are ______ ________, dividing the books into 128 sub-lines of ten would take about seven rounds, or 8,960 seconds. Sorting these sub-lines would add about 22 seconds each. All in all, this method known as QuickSort could sort the _____ in under three and a half _____. But there's a _____. Your __________ could end up lopsided, saving no time at all. Luckily, this rarely happens. That's why QuickSort is one of the most _________ __________ used by programmers today. They use it for things like sorting items in an ______ store by price, or creating a list of all the gas ________ _____ to a given location sorted by distance. In your case, you're done _____ _______ with time to spare. Just another high-stakes day in the library.

Solution

droves
hours
catch
partition
strategies
classes
sorted
loads
reach
adding
stations
online
sorting
middle
start
balanced
pretty
books
automatic
afternoon
called
efficient
strategy
leave
placing
partitions
quick
close
bubble

Original Text

You work at the college library. You're in the middle of a quiet afternoon when suddenly a shipment of 1,280 different books arrives. The books have been dropped of in one long straight line, but they're all out of order, and the automatic sorting system is broken. To make matters worse, classes start tomorrow, which means that first thing in the morning, students will show up in droves looking for these books. How can you get them all sorted in time? One way would be to start at one end of the line with the first pair of books. If the first two books are in order, then leave them as they are. Otherwise, swap them. Then, look at the second and third books, repeat the process, and continue until you reach the end of the line. At some point, you'll come across the book that should be last, and keep swapping it with every subsequent book, moving it down the line until it reaches the end where it belongs. Then, start from the beginning and repeat the process to get the second to last book in its proper place, and keep going until all books are sorted. This approach is called Bubble Sort. It's simple but slow. You'd make 1,279 comparisons in the first round, then 1,278, and so on, adding up to 818,560 comparisons. If each took just one second, the process would take over nine days. A second strategy would be to start by sorting just the first two books. Then, take the third book and compare it with the book in the second spot. If it belongs before the second book, swap them, then compare it with the book in the first spot, and swap again if needed. Now you've sorted the first three books. Keep adding one book at a time to the sorted sub-line, comparing and swapping the new book with the one before it until it's correctly placed among the books sorted so far. This is called Insertion Sort. Unlike Bubble Sort, it usually doesn't require comparing every pair of books. On average, we'd expect to only need to compare each book to half of the books that came before it. In that case, the total number of comparisons would be 409,280, taking almost five days. You're still doing way too many comparisons. Here's a better idea. First, pick a random book. Call it the partition and compare it to every other book. Then, divide the line by placing all the books that come before the partition on its left and all the ones that come after it on its right. You've just saved loads of time by not having to compare any of the books on the left to any of the ones on the right ever again. Now, looking only at the books on the left, you can again pick a random partition book and separate those books that come before it from those that come after it. You can keep creating sub-partitions like this until you have a bunch of small sub-lines, each of which you'd sort quickly using another strategy, like Insertion Sort. Each round of partitioning requires about 1,280 comparisons. If your partitions are pretty balanced, dividing the books into 128 sub-lines of ten would take about seven rounds, or 8,960 seconds. Sorting these sub-lines would add about 22 seconds each. All in all, this method known as QuickSort could sort the books in under three and a half hours. But there's a catch. Your partitions could end up lopsided, saving no time at all. Luckily, this rarely happens. That's why QuickSort is one of the most efficient strategies used by programmers today. They use it for things like sorting items in an online store by price, or creating a list of all the gas stations close to a given location sorted by distance. In your case, you're done quick sorting with time to spare. Just another high-stakes day in the library.

Frequently Occurring Word Combinations

ngrams of length 2

collocation	frequency
insertion sort	2

Important Words

add
adding
afternoon
approach
arrives
automatic
average
balanced
beginning
belongs
book
books
broken
bubble
bunch
call
called
case
catch
classes
close
college
compare
comparing
comparisons
continue
correctly
creating
day
days
distance
divide
dividing
dropped
droves
efficient
expect
gas
hours
idea
insertion
items
leave
left
library
line
list
loads
location
long
lopsided
luckily
matters
means
method
middle
morning
moving
needed
number
online
order
pair
partition
partitioning
partitions
pick
place
placing
point
pretty
price
process
programmers
proper
quick
quickly
quicksort
quiet
random
rarely
reach
reaches
repeat
require
requires
rounds
saved
saving
seconds
separate
shipment
show
simple
slow
small
sort
sorted
sorting
spare
spot
start
stations
store
straight
strategies
strategy
students
subsequent
suddenly
swap
swapping
system
ten
time
today
tomorrow
total
work
worse